package LinkTest;
import java.util.Stack;

public class LinkCountSum {
    static class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
 }
 //求两个链表的和并返回一个新链表
//第一种方式
    public static ListNode addInList2 (ListNode head1, ListNode head2) {
        // write code here
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        Stack<ListNode> s1=new Stack<>();
        Stack<ListNode> s2=new Stack<>();
        Stack<ListNode> s3=new Stack<>();
        while(head1!=null){
            s1.push(head1);
            head1=head1.next;
        }
        while(head2!=null){
            s2.push(head2);
            head2=head2.next;
        }
        int i=0;//进位变量
        while(!s1.isEmpty()||!s2.isEmpty()||i>0){//i>0有进位就执行不管栈是否为空
            int val1=s1.isEmpty()? 0:s1.pop().val;
            int val2=s2.isEmpty()?0:s2.pop().val;
            int sum=val1+val2+i;
            i=sum/10;
            ListNode n=new ListNode(sum%10);
            s3.push(n);

        }
        ListNode n2=new ListNode(0);
        ListNode n3=n2;
        while(!s3.isEmpty()){
            n3.next=s3.pop();
            n3=n3.next;//尾插
        }
        return n2.next;
    }
}
